//
// Created by francklinson on 2021/10/12 AT 10:53.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    int largestSumAfterKNegations(vector<int> &nums, int k) {
        priority_queue<int, vector<int>, greater<>> pq; // 用优先队列实现排列和最小值的保持
        for (auto &x: nums)
            pq.push(x);
        for (int i = 0; i < k; ++i) {
            auto x = pq.top();
            pq.pop();
            pq.push(-x);
        }
        int ans = 0;
        while (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
        return ans;
    }
};

class Solution2 {
public:
    int largestSumAfterKNegations(vector<int> &nums, int k) {
        unsigned int n = nums.size();
        sort(nums.begin(), nums.end()); // 排序
        int minIndex = 0;
        while (k > 0) {
            nums[minIndex] = -nums[minIndex];
            // 考虑是否要选择下一个minIndex
            if (minIndex < n - 1 && nums[minIndex] > nums[minIndex + 1]) {
                ++minIndex;
            }
            --k;
        }

        int res = 0;
        for (int num: nums) {
            res += num;
        }

        return res;
    }
};

int main() {
    vector<int> nums{4, 2, 3};
    Solution solution;
    cout << solution.largestSumAfterKNegations(nums, 1) << endl;
    return 0;
}

